package Leetcode.sliding_window;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


/**
 * @Author: kirito
 * @Date: 2024/3/30 15:15
 * @Description:
 * 滑动子数组的美丽值
 * 给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。
 *
 * 一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
 *
 * 请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。
 *
 * 子数组指的是数组中一段连续 非空 的元素序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
 * 输出：[-1,-2,-2]
 * 解释：总共有 3 个 k = 3 的子数组。
 * 第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
 * 第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
 * 第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。
 * 示例 2：
 *
 * 输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
 * 输出：[-1,-2,-3,-4]
 * 解释：总共有 4 个 k = 2 的子数组。
 * [-1, -2] 中第二小的数是负数 -1 。
 * [-2, -3] 中第二小的数是负数 -2 。
 * [-3, -4] 中第二小的数是负数 -3 。
 * [-4, -5] 中第二小的数是负数 -4 。
 * 示例 3：
 *
 * 输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
 * 输出：[-3,0,-3,-3,-3]
 * 解释：总共有 5 个 k = 2 的子数组。
 * [-3, 1] 中最小的数是负数 -3 。
 * [1, 2] 中最小的数不是负数，所以美丽值为 0 。
 * [2, -3] 中最小的数是负数 -3 。
 * [-3, 0] 中最小的数是负数 -3 。
 * [0, -3] 中最小的数是负数 -3 。
 *
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= n <= 105
 * 1 <= k <= n
 * 1 <= x <= k
 * -50 <= nums[i] <= 50
 *
 */

public class getSubarrayBeauty {
    public static void main(String[] args) {
        int[] arr = {1, -1, -3, -2, 3};
        int k = 3, x = 2;
        System.out.println(Arrays.toString(getSubarrayBeauty(arr, k, x)));
    }
    public static int[] getSubarrayBeauty(int[] nums, int k, int x) {
        // 获取数组的长度
        int length = nums.length;
        // 创建一个长度为101的数组，用于存储每个数字的出现次数
        // 由于数组索引从0开始，而代码中使用的是nums[i] + 50，所以需要一个长度为101的数组来存储0到50的数字出现次数
        int[] count = new int[101];

        // 初始化count数组，用于存储窗口内前k-1个元素的出现次数
        for (int i = 0; i < k - 1; i++) {
            count[nums[i] + 50]++;
        }

        // 创建结果数组，其长度为原数组长度减去k加1
        int[] res = new int[length - k + 1];
        // 结果数组的索引
        int index = 0;

        // 从第k个元素开始遍历数组
        for (int right = k - 1; right < length; right++) {
            // 当前元素进入窗口，计数增加
            count[nums[right] + 50]++;

            // 初始化当前的美丽值为x
            int now = x;
            // 初始化临时变量temp为0
            int temp = 0;

            // 遍历-50到0的数字，寻找美丽值
            for (int i = 0; i < 50; i++) {
                // 减去窗口外一个元素的出现次数
                now -= count[i];
                // 如果now小于等于0，说明找到了美丽值
                if (now <= 0) {
                    // 计算美丽值的绝对值
                    temp = i - 50;
                    // 跳出循环
                    break;
                }
            }

            // 将计算出的美丽值存入结果数组
            res[index++] = temp;

            // 当前窗口外的一个元素离开窗口，计数减少
            count[nums[right - k + 1] + 50]--;
        }

        // 返回结果数组
        return res;
    }

}
